Tags: binary search
Consider the code below, which shows binary_search as discussed in lecture, but with one additional line: a print statement.
import math
def binary_search(arr, t, start, stop):
if stop - start <= 0:
return None
middle = math.floor((start + stop)/2)
print(arr[middle]) # <---- this line is new
if arr[middle] == t:
return middle
elif arr[middle] > t:
return binary_search(arr, t, start, middle)
else:
return binary_search(arr, t, middle+1, stop)
Suppose this version of binary search is called on an array and with a target of t = 7. Which of the following statements is true?
Some of the printed values may be less than or equal to 7, and some may be greater than or equal to 7.
Tags: binary search, verifying recursion
Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number \(x\) is the smallest integer that is \(\geq x\)). The full code is shown below for convenience:
import math
def new_binary_search(arr, start, stop, target):
if stop <= start:
return None
middle = math.ceil((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] < target:
return new_binary_search(arr, middle + 1, stop, target)
else:
return new_binary_search(arr, start, middle, target)
Which of the following statements about the correctness of new_binary_search is true? You may assume that arr will be a list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop
= len(arr) - 1.
new_binary_search may recurse infinitely
Tags: binary search, recursion
Suppose binary_search has been called on an array arr with a target t that is not necessarily in the array, and with start and stop indices start and stop, respectively (remember, our convention is that the start index is included, while the stop index is excluded from the search). Which of the following must be true? Mark all which apply. You may assume that stop - start\(\geq 1\).
Note: remember that any statement about an empty array is considered to be automatically true. Also, you cannot assume that this call to binary_search is the root call (it could be a recursive call).
The last two answers are both correct.
Tags: binary search, recursion
Suppose binary_search is called on a sorted array of size \(n\). In total, how many recursive calls to binary_search are made in the worst case?
\(\Theta(\log n)\)
Tags: binary search
Consider the problem of searching for an element t in a sorted array, with the added requirement that if t is in the array multiple times, we return the index of the first occurrence. For example, if arr = [3, 4, 4, 4, 5, 8], and t = 4, the code should return 1, since the first 4 is at index one.
binary_search as implemented in lecture may not necessarily return the index of the first occurrence of t, but it can be modified so that it does.
Fill in the blanks below so that the function returns the index of the first occurence of t. Hint: last_seen should keep track of the index of the last known occurrence of t.
import math
def mbs(arr, t, start, stop, last_seen=None):
if start - stop <= 0:
return last_seen
middle = math.floor((stop - start) / 2)
if arr[middle] == t:
# _________ <-- fill this in
elif arr[middle] < t:
# _________ <-- fill this in
else:
# _________ <-- fill this in
Here is how the blanks should be filled in:
if arr[middle] == t:
return mbs(arr, t, start, middle, middle)
elif arr[middle] < t:
return mbs(arr, t, middle + 1, stop, last_seen)
else:
return mbs(arr, t, start, middle, last_seen)
If we see arr[middle] == t, we know that this is either the first occurrence of t in the array, or the first occurrence of t in the left half of the array. Therefore, we make a recursive call to mbs on the left half of the array, keeping track of middle as the index of the leftmost occurrence of t we have seen so far (this is done by passing it as the value to last_seen).
The other recursive calls are the same as in the original binary_search function, except that we pass last_seen as an argument to the recursive calls. This is because we want to keep track of the leftmost occurrence of t we have seen so far.
Eventually, we will reach a point where start - stop <= 0. At this point, we return last_seen, which is the index of the leftmost occurrence of t we have seen so far. This will necessarily be the leftmost occurrence of t in the array.
Tags: binary search
Consider the version of binary search shown below:
import math
def binary_search(arr, t, start, stop):
"""
Searches arr[start:stop] for t.
Assumes arr is sorted.
"""
if stop - start <= 0:
return None
middle = math.floor((start + stop)/2)
if arr[middle] == t:
return middle
elif arr[middle] > t:
return binary_search(arr, t, start, middle)
else:
return binary_search(arr, t, middle+1, stop)
True or false: if the target element t occurs multiple times in the array, binary_search is guaranteed to return the first occurrence.
You may assume that arr is sorted and that binary_search(arr, t, 0, len(arr)) is called.
False.
Tags: binary search, loop invariants
Consider the iterative implementation of binary search shown below:
import math
def iterative_binary_search(arr, target):
start = 0
stop = len(arr)
while (stop - start) > 0:
print(arr[start])
middle = math.floor((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] > target:
stop = middle
else:
start = middle + 1
return None
Which of the following loop invariants is true, assuming that arr is sorted and non-empty, and target is not in the array? Select all that apply.
The first option is correct.
Tags: binary search, loop invariants
Consider iterative_binary_search below and note the print statement in the while-loop:
import math
def iterative_binary_search(arr, target):
start = 0
stop = len(arr)
while (stop - start) > 0:
print(arr[start])
middle = math.floor((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] > target:
stop = middle
else:
start = middle + 1
return None
Suppose iterative_binary_search is run on the array:
[-202, -201, -200, -50, -20, -10, -4, -3, 0, 1, 3, 5, 6, 7, 9, 10, 12, 15, 22]
with target 11.
What will be the last value of arr[start] printed?
10
Tags: binary search, recursion, verifying recursion
Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number \(x\) is the smallest integer that is \(\geq x\)). The full code is shown below for convenience:
import math
def new_binary_search(arr, start, stop, target):
if stop <= start:
return None
middle = math.ceil((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] < target:
return new_binary_search(arr, middle + 1, stop, target)
else:
return new_binary_search(arr, start, middle, target)
You may assume that arr will be a sorted list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop = len(arr).
True or False: there are input arrays on which new_binary_search will recurse infinitely.
True.
True or False: there are input arrays on which new_binary_search will raise an IndexError because it attempts to access an element of the array which does not exist.
True.